package com.zwj.interview.DFS;



/**
 * 在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。
 * 路径中至少包含一个节点，不一定经过二叉树的根节点，也不一定经过叶节点。
 * 给定非空的一棵二叉树，请求出二叉树所有路径上节点值之和的最大值
 *
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/java-zhuan-ti-jiang-jie-di-gui-si-lu-qin-qx8a/
 */
public class 路径和最大值again {

    int maxRes = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        postOrder(root);
        return maxRes;
    }

    /**
     拿到一边，包括该root的最大sum
    */
    private int postOrder(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = Math.max(postOrder(root.left), 0);
        int right = Math.max(postOrder(root.right), 0);
        //对于任意一个节点，其路径的值就等于节点的值加上其左右子树的节点值
        maxRes = Math.max(maxRes, root.val + left + right);
        //这里返回的是任意节点的某一边的路径最大值，或左边或右边
        return root.val + Math.max(left, right);
    }











}
